NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c++-part1/8494

Internet Message Format | 1996-08-05 | 4.0 KB

Path: moalla.trin.cam.ac.uk!93bb
From: [e-mail] (Ben Blaukopf)
Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
Subject: Re: Tough FACTORIAL math problem...
Date: Thu, 15 Feb 1996 18:07:23
Organization: University of Cambridge, England
Message-ID: <[e-mail]>
References: <4fr8be$[e-mail]> <[e-mail]> <4fv74c$[e-mail]>
NNTP-Posting-Host: moalla.trin.cam.ac.uk
X-Newsreader: Trumpet for Windows [Version 1.0 Rev A]

In article <4fv74c$[e-mail]> [e-mail] (Sven Pran) writes:
>From: [e-mail] (Sven Pran)
>Subject: Re: Tough FACTORIAL math problem...
>Date: Thu, 15 Feb 96 11:50:11 GMT

>In article <[e-mail]>, John Cleland <[e-mail]> wrote:
>>The Crow wrote:
>>>
>>> Here is what I am trying to do, I want to find the last NON-ZERO digit of a
>>> given factorial.  For instance,
>>>
>>> 5! = 120
>>>
>>> so the last non-zero digit is 2.  I want to be able to do this up to 1000.
>>> Problem is, no matter how huge of a data-type you use, there isn't any way
>>> for the computer to handle 1000!, it is however possible to find the last
>>> non-zero digit somehow.  One thing I have tried is as I went through
>>> multiplying the series of numbers in the factorial (5 * 4 * 3 * 2) I would
>>> remove all the trailing ZEROS, I got this to work up to 789, but it wont
>>> work with 1000 and i am not really sure why.  If anyone has a clue how I
>>> can do this let me know.
>>
>>Don't just strip the trailing zeros, remove all digits except the last
>>non-zero digit (which is your output) and then multiply by the next number in
>>your sequence. This keeps the numbers down to a managable level and gives the
>>correct answer as no more significant digit can affect the value of the LSD.
>>
> . . . .

>No, it is obviously not sufficient to keep the last single non-zero digit, and
>the problem appears to be a very interesting and intriguing one:

>A new trailing zero is 'created' every time the next multiplier is divisible
>by 5, and how can we then calculate the next 'rightmost significant' digit?

>Example when a multiplier ends in 05:

>If the 'previous' factorial ended in 02 then the new factorial will end in 1
>while if it ended in 12 then the new factorial will end in 6 (after removal of
>trailing zeroes).

>Thus the SINGLE rightmost significant digit in the new factorial depends upon
>the TWO rightmost significant digits both in the previous factorial and in the
>multiplier.

>This means that we must keep track of the last TWO digits to calculate the new
>SINGLE rightmost significant digit whenever a zero is 'created'. For similar
>reasons we must track THREE digits to calculate the new TWO rightmost
>significant digits - and so on.

>How many zeroes have been 'removed' when we reach 1000! ? The answer is 249,
>which means that in order to maintain the precision needed we must track the
>last 250 digits less the number of zeroes already 'removed' when N! reaches a
>number with that many digits.

>This is where I get stuck. Hey - number theory specialists: How do we proceed?

>regards Sven
Since we are programming this, rather than it being a pure maths problem,
there are a lot of shortcuts we can look out for.

of each number in the factorial, only the rightmost digit is significant, so
for example 85 is equivalent to 5.

so 85! is equivalent to (10!)^8 * 5!
but of course only the right-hand few digits of 10! are at all significant.

1.9 = 9 (right most non-zero digit)
9.8 = 2
2.7 = 4
4.6 = 4
4.5 = 2
2.4 = 8
8.3 = 4
4.2 = 8
8.1 = 8

So (10a+b)! = 8^a * b! (when dealing with least significant non-zero digit)

8.8 = 64 (10!)
4.8 = 32 (20!)
2.8 = 16 (30!)
6.8 = 48 (40!)

therefore the whole thing cycles round every forty digits. note that this does
not mean that the last digit of 45! is the same as that of 5!, you have to
reach 10!. So 50! is equivalent to 10!, and all numbers up - (50+a)! is
equivalent to (10+a)!.

This should help!!!

Ben Blaukopf
[e-mail]